This invention relates to the use of arrays of linkable circulating storage loops and, more particularly, to the use of said arrays for sorting of records so as to produce an arrangement of records whose corresponding keys obey a specified linear ordering.
The importance of sorting in data processing is a matter of common knowledge. Typically, one deals with a set of records {R.sub.i}, i = 0, 1, 2, . . . (N-1) and corresponding keys {K.sub.i}. The records need to be arranged in a linear sequence in the order of the keys. Whenever two keys are rated as equal, some tie-breaking procedure is invoked. The keys can be embedded entirely within the records, to be sampled dynamically whenever comparison is needed. Alternatively, the keys may lie outside the records in some form more accessible to the control mechanism with a one-to-one correspondence to the records. Often the keys are embedded in the records, but duplicate copies of the keys are used for the ordering.
Reference is made to H. Chang et al, U.S. patent application Ser. No. 556,378, filed Mar. 7, 1975, entitled "Ladder for Information Processing". This reference describes information processing achieved by a structure using a dual mode switch. The switch can steer two data streams so that they will either cross one another or bypass one another, depending upon external control. A linear array of shift register loops can be linked together by means of these flow steering binary switches to form a storage structure termed a ladder. A similar ladder structure results from the use of an alternative switch having two orthogonal bypass modes.
The ladder provides a variety of information handling modes. For example, the ladder can dynamically rearrange records according to recency of usage in order to improve average access time to any record. The binary switch and the ladder structure are implementable using magnetic bubble domain technology.
In Chang et al, the ladder is described in detail. Since each loop has no more than two adjacent, switchably interconnecting neighbor loops, then upon any boundary switch being set into a first mode or "on", the two adjacent loops linked by said switch are cross-connected thereby enabling an exchange of any records circulating therein. When the two boundary switches to any given loop are set into a second mode or "off", ten the loop is maintained as a circulating path.
Reference is also made to T. C. Chen et. al. U.S. Pat. No. 3,997,880 issued on Dec. 14, 1976 based on an application filed on Mar. 7, 1975, entitled "Apparatus and Machine Implementable Method for the Dynamic Rearrangement of Plural Bit Equal Length Records". In this second reference, there is described an apparatus for performing efficient permutations of equal length records. This apparatus, as in the first reference, also takes advantage of the flow steering property of linkable storage loops. It is directed to the dynamic ordering of fixed length records among loops that are linearly linked with aforesaid flow steering switches. Another description may be found in T. C. Chen and C. Tung, "Storage Management Operations in Linked Uniform Shift Register Loops", IBM Journal of Research and Development, March 1976, pages 123-131.
Both references, while using switchable linearly linked loops, are nevertheless distinquished from each other. In the first reference, all but one of the loops are double-sized, each holding two records except for the top loop which holds a single record. Further, in the first reference, all the switches linking the double size loops are set in the same mode. In the second reference, all loops are of equal length with each one holding but one record, and all switches are freely set. The freedom of switching can then be exploited, for example, to migrate a record dynamically over D loop levels, taking (D+1)/2 periods, a period being the time required for one data bit to make one revolution around a loop with the boundary switches off.